package 数据结构.LinkList.diamond;
//leetcode：160 相交链表
public class getIntersectionNode {
    public static class ListNode{
        int val;
        ListNode next;
        ListNode(int x) {
            val = x;
            next = null;
        }
    }
    // 创建链表的辅助方法
    public static ListNode createLinkedList(int[] values) {
        if (values == null || values.length == 0) return null;
        ListNode head = new ListNode(values[0]);
        ListNode current = head;
        for (int i = 1; i < values.length; i++) {
            current.next = new ListNode(values[i]);
            current = current.next;
        }
        return head;
    }

    public static void main(String[] args) {
        ListNode headA = createLinkedList(new int[]{1});
        ListNode headB = createLinkedList(new int[]{1});
        getIntersectionNode(headA,headB);

    }
    //直接走两个链表的长度差
    //1--2--3--5--6
    //7--4--9--3--5--6
    public static ListNode getIntersectionNode(ListNode headA, ListNode headB) {
   //复杂度分析：时间复杂度：O(N+M)
        //空间复杂度：O(1)

    int lenA=0;
    int lenB=0;
    ListNode temA=headA;
    ListNode temB=headB;
    while (temA!=null){
        lenA++;
        temA=temA.next;
    }
    while (temB!=null){
        lenB++;
        temB=temB.next;
    }
    int dif=0;
    if(lenA>lenB){
        dif=lenA-lenB;
        for (int i = 0; i < dif; i++) {
                headA=headA.next;
        }
    }else {
        dif=lenB-lenA;
        for (int i = 0; i < dif; i++) {
                headB=headB.next;
        }
    }
    while (headA!=null){
        if(headA==headB){
            return headA;
        }
        headA=headA.next;
        headB=headB.next;
    }

return null;
    }
}
